package _dp_base;

/**
 * 188. 买卖股票的最佳时机 IV
 */
public class No188 {
    private int[] prices;

    /**
     * 1. 递归
     */
    public int maxProfit1(int k, int[] prices) {
        this.prices = prices;
        int n = prices.length;

        return dfs(n - 1, k, 0);
    }

    private int dfs(int i, int j, int hold) {
        if (j < 0) return Integer.MIN_VALUE;
        else if (i < 0) return hold == 0 ? 0 : Integer.MIN_VALUE;
        else if (hold == 0) return Math.max(dfs(i - 1, j, 0), dfs(i - 1, j - 1, 1) + prices[i]);
        else return Math.max(dfs(i - 1, j, 0) - prices[i], dfs(i - 1, j, 1));
    }

    /**
     * 2. 迭代
     */
    public int maxProfit2(int k, int[] prices) {
        int n = prices.length;
        int[][][] f = new int[n + 1][k + 2][2];
        for (int j = 0; j < f[0].length; j++) {
            f[0][j][1] = Integer.MIN_VALUE;
        }
        for (int i = 0; i < n; i++) {
            f[i][0][0] = Integer.MIN_VALUE;
            f[i][0][1] = Integer.MIN_VALUE;
            for (int j = 0; j < k + 1; j++) {
                f[i + 1][j + 1][0] = Math.max(f[i][j + 1][0], f[i][j][1] + prices[i]);
                f[i + 1][j + 1][1] = Math.max(f[i][j + 1][0] - prices[i], f[i][j + 1][1]);
            }
        }
        return f[n][k + 1][0];
    }

    /**
     * 4. 空间优化
     */
    public int maxProfit4(int k, int[] prices) {
        int[][] f = new int[k + 2][2];
        for (int j = 0; j < f.length; j++) {
            f[j][1] = Integer.MIN_VALUE;
        }
        f[0][0] = Integer.MIN_VALUE;
        for (int price : prices) {
            for (int j = 0; j < k + 1; j++) {
                int temp = Math.max(f[j + 1][0], f[j][1] + price);
                f[j + 1][1] = Math.max(f[j + 1][0] - price, f[j + 1][1]);
                f[j + 1][0] = temp;
            }
        }
        return f[k + 1][0];
    }
}
